
In perioada 28.04-2.05 s-a desfasurat la Lugoj Concursul National de Soft 
"Grigore Moisil", editia a VI-a, organizat de Clubul Elevilor Lugoj.

Concursul a fost constituit din doua sectiuni:
- Sectiunea de comunicari stiintifice, organizata pe doua niveluri 
(gimnaziu si liceu)
- Sectiunea de programare, organizata pe 4 niveluri (clasele V-VI, VII-VIII, 
IX-X, XI-XII).

Ca in fiecare an, organizatorii au reusit sa asigure toate conditiile necesare 
desfasurarii unui concurs national de nivel inalt. Eforturile lor  sunt 
rasplatite prin satisfactia ca toti elevii se pot considera castigatori,
prin privilegiul de a fi participat la o astfel de manifestare.

Presedintele comisiei de jurizare si propuneri de subiecte a fost d-l prof. 
univ. dr. Stelian Niculescu- Universitatea Politehnica Bucuresti.

Comisia a fost alcatuita din:

- lector univ. Gheorghe Petrov- Universitatea Timisoara
- prof. Rodica Pintea -         Liceul "Gr. Moisil" Bucuresti
- prof. Emanuela Cerchez-       Liceul de Informatica "Gr.Moisil" Iasi
- prof. Marinel Serban -        Liceul de Infromatica "Gr.Moisil" Iasi.
- mat.  Ivan Bloch -            Lugoj

La aprecierea lucrarilor prezentate in cadrul sectiunii de comunicari 
stiintifice au mai facut parte din comisie si prof. Felicia Neacsu, de la 
Liceul de Informatica Timisoara si ing. Emil Munteanu, Lugoj.

In continuare, prezentam subiectele precum si lista castigatorilor concursului.

Concursul National de Soft "Grigore Moisil"
Lugoj, 28.04-02.05.1999
Clasele V-VI

Problema 1 - Problema bibliotecarului - 50 puncte

    Bibliotecarul de la scoala ta a descoperit o carte in care paginile
care ar fi trebuit sa fie numerotate cu un numar prim aveau numarul de pagina
complet mazgalit. Stiind ca numerotarea paginilor cartii incepe de la 3,
scrieti un program care citeste de la tastatura pe n, numarul de pagini din
carte (n <= 30000) si afiseaza pe ecran numarul de pagini nemazgalite, precum
si numarul de cifre pe care trebuie sa le scrie bibliotecarul, pentru a
reconstitui numerotarea paginilor mazgalite.

De exemplu, pentru n = 10, programul afiseaza pe ecran:

Numarul de pagini nemazgalite este 7
Bibliotecarul trebuie sa scrie 3 cifre

Timp maxim de executie: 1 minut / test.

Problema 2 - Bile - 50 puncte

    Pe o masa de tip biliard sunt dispuse n bile numerotate de la 1 la n
(n <= 30 citit de la tastatura). Bilele sunt eliminate de pe masa una cate
una, fiecare bila eliminata fiind luata de un "baiat de bile" si pusa
intr-un sir. Baiatul de bile incearca sa plaseze fiecare bila nou eliminata
exact la mijlocul sirului de bile deja format (numarul de bile din fata sa
fie egal cu numarul de bile de dupa aceasta). Cand acest lucru nu este
posibil, atunci el o plaseaza la sfarsitul sirului de bile.
Scrieti un program care sa citeasca de la tastatura numarul de bile, apoi 
ordinea finala a bilelor in sir si care sa afiseze pe ecran numerele
bilelor, in ordinea in care au fost ele eliminate de pe masa de biliard,
separate prin spatii.

Exemplu:
n=7
sirul final = 1  7  2  5  3  4  6

Bilele sunt eliminate in ordinea
1 3 7 4 2 6 5

Timp maxim de executie: 1 secunda/test.

Timp de lucru 2 ore si 30 minute.


Lugoj, 28.04-02.05.1999
Clasele VII-VIII

Problema 1 - Spion - 50 puncte

Sa se scrie un program care sa poata codifica sau decodifica un mesaj.
La codificare, din fiecare linie a mesajului necodificat se codifica intreaga
linie sau primele 80 de caractere (cele in plus, eventual existente la
codificare in fisierul de intrare, fiind ignorate).
Caracterele din mesajul necodificat sunt litere mari, litere mici ale 
alfabetului, caracterele ,  .  :  ;  ?  ! sau caracterul spatiu, deci sunt
recunoscute caracterele (cu codurile ASCII asociate):
     "A"  65        "a"  97         " "  32
     "B"  66        "b"  98         "!"  33
      .                 .           ","  44
      .                 .           "."  46
      .                 .           ":"  58
     "Z"  90        "z"  122        ";"  59
                                    "?"  63
Orice alt caracter este ignorat.
Codificarea se face dupa urmatorul algoritm: fiecare linie care se codifica
se scrie in ordine inversa, inlocuindu-se fiecare caracter cu sirul rezultat
prin transformarea codului ASCII al caracterului respectiv in sir de
caractere scris in ordine inversa. Astfel, daca mesajul este Az, mesajul
codificat va fi sirul 22156. In mesajul codificat nu apar spatii.

Numele fisierului care contine mesajul de codificat/decodificat este
SPION.IN, iar cel al fisierului de iesire, care va contine mesajul
codificat/decodificat, este SPION.OUT. Prin cercetarea fisierului de
intrare se stabileste operatia care trebuie facuta asupra acestuia
(codificare/decodificare).

Exemple:
Daca fisierul de intrare SPION.IN va contine mesajul (necodificat):
abc
Concursul National de Soft "Grigore Moisil", Lugoj, 1999!

fisierul de iesire SPION.OUT va contine:
998979
33234460111130171167234480150151150111177231014111113015014111723611201111382310100123801790111115016117987238017115114117119901111176

si invers daca fisierul de intrare SPION.IN va fi:
998979
33234460111130171167234480150151150111177231014111113015014111723611201111382310100123801790111115016117987238017115114117119901111176

fisierul de iesire SPION.OUT va contine:
abc
Concursul National de Soft Grigore Moisil, Lugoj, !

Timp maxim de executie: 1 secunda/test


Concursul National de Soft "Grigore Moisil"
Lugoj, 28.04-02.05.1999
Clasele VII-VIII

Problema 2 - Operatii - 50 puncte

Se considera un enunt de forma "adun 5 scad 8 inmultesc cu 3 impart la 2".
Pentru un numar initial, se aplica enuntul in mod repetat notandu-se toate
rezultatele partiale. De exemplu, pentru valoarea de pornire 5, prin
aplicarea de doua ori a enuntului, se obtine sirul de rezultate partiale:
5    10    2    6    3    8    0    0    0
 (+5)  (-8) (x3) (:2) (+5) (-8) (x3) (:2)
Se considera un sir de rezultate partiale (inclusiv termenul initial). Sa
se determine cel mai scurt enunt (ca numar de operatii) care l-a generat.
Datele de intrare se citesc din fisierul text OPER.IN, iar rezultatele se
scriu in fisierul OPER.OUT.
Se citeste de pe prima linie a fisierului de intrare numarul n de termeni
ai sirului (n <= 200), pe urmatoarele n linii aflandu-se termenii sirului,
numere naturale de cel mult 5 cifre, cate unul pe linie.
Se scriu in fisierul de iesire, cate una pe linie, operatiile ce formeaza
enuntul, o operatie fiind specificata printr-un singur caracter din multimea
{+, -, x, :} urmat imediat de un numar natural. Operatorii +, - desemneaza
operatorul de adunare, respectiv scadere, x desemneaza operatorul de imnultire, 
iar : este operatorul de impartire exacta in multimea numerelor naturale.

Exemplu:
OPER.IN
7
24
8
15
5
12
4
11
OPER.OUT
:3
+7

Explicatie:
sirul are 7 termeni
Enuntul "impart la 3, adun 7" se aplica de 3 ori
24 -> 8 -> 15 -> 5 -> 12 -> 4 -> 11
   :3   +7    :3   +7    :3   +7

Timp maxim de executie: 1 secunda/test
Timp de lucru pentru ambele probleme: 3 ore.

Concursul National de Soft "Grigore Moisil"
Lugoj, 28.04-02.05.1999
Clasele IX- X

Problema 1 - Joc cu trenuletul - 50 puncte

Intr-un joc cu trenuletul, dintr-o eroare de proiectare,liniile pot fi
montate doar intr-un singur mod:
- o linie de intrare din care se desprind intr-un nod
- k linii de manevra care se vor uni in alt nod intr-
- o linie de iesire
                           manevra 1
                     / ----------------------\
                   /       manevra 2           \
    intrare      /  / ----------------------- \  \   iesire
    ---------->o /  . . .                      
\o\------------>
                 \                               /
                   \       manevra k           /
                     -------------------------

Jucandu-se, un copil aseaza pe linia de intrare o garnitura de tren cu n
vagoane numerotate de la 1 la n, cu vagoanele asezate intr-o ordine oarecare;
vagoanele intra cate unul pe liniile de manevra, deplasarea putandu-se face
intr-un singur sens, de la intrare spre iesire; copilul doreste sa obtina
garnitura de tren cu care se joaca in ordinea crescatoare a numarului
vagoanelor. Ajutati-l!

INTRARE:
Fisierul text TREN.IN cu structura:
n k             - numarul de vagoane, numarul de linii de manevra
despartite printr-un spatiu (1 <= n, k <= 200)
v1  v2  ...  vn - cele n vagoane pe linia de intrare
despartine prin cate un spatiu

IESIRE:
Fisier text TREN.OUT cu structura:
X1  V1  L1  P1   Xi caracterul "M" sau "O", cu semnificatia
X2  V2  L2  P2     M - mutarea se face de pe linia de intrare pe cea de manevra
X3  V3  L3  P3     O - mutarea se face de pe linie de manevra pe cea de iesire
..               Vi numar vagon
Xp  Vp  Lp  Pp   Li linia de manevra pe/de pe care se muta vagonul
                 Pi pozitia din linie pe care se muta vagonul

sau mesajul
VAGOANELE NU SE POT MUTA

EXEMPLU:
pentru fisierul de intrare:
5 3
1 3 5 4 2

fisierul de iesire TREN.OUT poate fi:
M 1 1 1         vagonul 1 se muta pe linia de Manevra 1 pe pozitia 1
O 1 1 1         vagonul 1 se muta de pe linia de manevra 1 la iesire (O) pe pozitia 1
M 3 1 1         ...
M 5 2 1
M 4 1 2
M 2 3 1
O 2 3 2
O 3 1 3
O 4 1 4
O 5 2 5

TIMP MAXIM DE EXECUTIE: 1 secunda/test

Concursul National de Soft "Grigore Moisil"
Lugoj, 28.04-02.05.1999
Clasele IX- X

Problema 2 - Robot - 50 puncte

Pe o suprafata rectangulara constituita din 20000x20000 de patratele unitare
se afla n containere cu produsele finite ale unei fabrici de jucarii, fiecare
container aflandu-se intr-o patratica unitara a retelei. 
Dupa o zi de lucru, in fiecare container i se afla un numar pi de produse
finite (pi numar natural de 1-2 cifre, pi > 0).
Un robot se deplaseaza pe niste sine aflate pe tavan, pe directii paralele cu
liniile sau coloanele retelei, pe deasupra containerelor, culegand produsele
din containere. Robotul porneste pe o linie sau o coloana a retelei, de pe
marginea retelei, (o coordonata fiind 0, pentru a specifica faptul ca punctul
de plecare este din afara retelei), el putandu-se opri pentru a aduna
produsele dintr-un container, sau pentru a-si schimba directia cu 90, 180 sau
270 de grade, sau pentru ambele operatii. Deci schimbarea de directie se
poate face numai in momentul in care robotul este coborat deasupra unui
container.
Stiind ca robotul este programat pentru un singur traseu, traseu dupa care
produsele neculese de robot vor fi adunate manual, sa se determine acest
traseu astfel incat numarul de produse ramase neculese de pe suprafata
retelei sa fie minim.
Traseul va fi descris pornind de la pozitia de plecare de pe marginea retelei
cu revenire in acelasi loc, pozitiile intermediare fiind o succesiune de
opriri ale robotului deasupra containerelor pentru culegeri, intoarceri sau
culegeri si intoarceri. Un container pe deasupra caruia se trece fara oprire
nu va fi mentionat in traseu.

Datele de intrare se citesc din fisierul ROBOT.IN, avand
urmatoarea structura:
n           -numarul de containere (n <= 200)
l1 c1 p1    -linia si coloana unde este amplasat si nr.de produse din containerul 1
..
ln cn pn    -linia si coloana unde este amplasat si nr.de produse din containerul n

Datele de iesire  se vor afisa in fisierul ROBOT.OUT sub forma:
p       - numarul de produse ramase pentru a fi culese manual
k       - numarul total de opriri (punctul de plecare, containerele vizitate, 
         nu neaparat distincte si punctul de revenire)
l1 c1       - pozitia de plecare de pe margine
l2 c2       - pozitia primului container vizitat
..
lk-1 ck-1   - pozitia ultimului container vizitat
lk ck       - pozitia de revenire (lk=l1, ck=c1)

Exemplu:
ROBOT.IN
6
3 3 2
2 1 8
3 4 5
3 5 1
3 6 1
8 4 3
ROBOT.OUT
8
9
3 0
3 3
3 4
3 5
3 6
3 4
8 4
3 4
3 0

Timp maxim de executie: 1 secunda/test.
Timp de lucru: 2 ore 30 minute (pentru ambele probleme)

Concursul National de Soft "Grigore Moisil"
Lugoj, 28.04-02.05.1999
Clasele XI- XII

Problema 2 - Ferma animalelor - 50 puncte

Desi primul din cele 7 precepte era "Orice merge pe doua picioare e dusman,
porcii au hotart ca e timpul sa exporte din productia de pertinax de la
ferma. Au ncheiat la oras n (1 <= n <= 5000) contracte pentru cantitatile
a1, a2, ..., an. Tovarasul Squeler a desemnat pentru fiecare contract cte
un porc, care urma sa coordoneze tranzactia si sa ncaseze banii, si n magari
care urmau sa transporte pertinaxul la oras. Transportul era totusi o
problema, pentru ca magarul este un animal cu un foarte dezvoltat simt al
dreptatii: nici un magar nu ar fi vrut sa transporte un bit mai mult dect
ceilalti. S-a hotart deci ca se vor face mai multe transporturi, astfel
nct la fiecare transport toti magarii disponibili sa transporte o aceeasi
cantitate. Dupa fiecare transport, porcii ai caror pertinax a fost transportat
integral urmau sa ramna n oras mpreuna cu magarii lor, pentru a finaliza
afacerea. Din acest motiv, cantitatea de pertinax aferenta unui contract nu
poate fi transportata partial.
Scrieti un program care sa determine o modalitate de mpartire a pertinaxului
pe transporturi.

Restrictii de intrare:
Datele de intrare se citesc din fisierul de intrare Ferma.in.
Pe prima linie se afla n, numarul de contracte ncheiate. Pe urmatoarele n
linii se gasesc cantitatile contractate a1, a2, ..., an, 
(ai din {1, 2, ..., 10 000}, (i din {1, 2, ..., n}), cte o una pe linie.

Restrictii de iesire:
Rezultatele vor fi afisate n fisierul Ferma.out.
Fisierul de iesire va contine mesajul "NU EXISTA SOLUTIE" sau va contine pe
prima linie numarul de transporturi efectuate t; pe urmatoarele linii sunt
afisate cele t transporturi. Pentru fiecare transport este afisat pe prima
linie nt, numarul de contracte onorate la transportul respectiv, iar pe
urmatoarele nt linii cantitatile de pertinax contractate.

Exemplu:
Pentru fisierul de intrare:
7
13
2
4
29
17
6
10

Iesirea va fi:
3
3
2
4
29
2
6
10
2
13
17

Nota:
Cantitatile a1, a2, ..., an sunt exprimate n MwKhTx. Un MwKhTx de pertinax
este indivizibil.
Timp de executie: 1 secunda per test.


Concursul National de Soft "Grigore Moisil"
Lugoj, 28.04-02.05.1999
Clasele XI-XII

Problema 1 - La peticeala - 50 puncte


La gradinita, Vasilica a invatat sa coase. Doamna educatoare i-a dat petice
dreptunghiulare de material de diferite culori si o bucata de panza alba, tot
de forma dreptunghiulara pe care Vasilica trebuie sa coase peticele,
asezandu-le cu laturile paralele cu laturile bucatii de panza. Doamna
educatoare i-a spus ca are voie, daca vrea, sa coase un petic peste altul.
Dupa ce si-a terminat opera, Vasilica o duce doamnei educatoare si o intreaba
ce suprafata a reusit el sa acopere cu petice. Scrieti un program care sa
determine aria acoperita de Vasilica cu petice.

Restrictii de intrare:
Datele de intrare se citesc din fisierul PETICE.IN care are urmatoarea
structura:
n
x11 y11 x12 y12
x21 y21 x22 y22
..
xn1 yn1 xn2 yn2

cu semnificatia:
n = numarul de petice (n < 100)
(xi1, yi1) si (xi2, yi2) (xi1, xi2, yi1, yi2 din R+) reprezinta coordonatele
                          a doua colturi opuse ale unui petic, relative la un
                          sistem de coordonate cartezian cu centrul in coltul
                          stanga jos al bucatii de panza alba si cu axele de
                          coordonate de-a lungul laturilor panzei. Lungimile
                          laturilor panzei albe nu depasesc 10000.

Restrictii de iesire:
Fisierul de iesire PETICE.OUT contine pe prima linie suprafata zonei acoperite
de petice, calculata cu 3 zecimale cu rotunjire.

Exemplu:
Pentru fisierul de intrare PETICE.IN:
2
0 0 4 5
3 4 10 10
Fisierul de iesire PETICE.OUT contine:
61.000

Timp maxim de executie: 1 secunda/test.


REZULTATE
SECTIUNEA - COMUNICARI STIINTIFICE

1. GIMNAZIU
LOCUL I       COSTAN VICTOR  SC.59 BUCURESTI
LOCUL II      PETROVAN BOGDAN  CC REGHIN
LOCUL III     MIHAI CRISTIAN  PC BOTOSANI
LOCUL III     BRA CATALIN  CC GIURGIU
MENTIUNE      BERINDE RADU  PNC BUCURESTI
PREMIU SPECIAL  SALGAU CATALIN  PC VASLUI

2. LICEU
LOCUL I       RASZGA CALIN  LIC.INF.TIMISOARA
LOCUL II      CHIRITA DANIEL  LIC.INF.TIMISOARA
LOCUL III     ANDREI MARIUS  SC.59 BUCURESTI
LOCUL III     PATRASCU MIHAI  PC CRAIOVA
MENTIUNE I    BRUDIU BOGDAN  LIC.INF.TIMISOARA
MENTIUNE II   BRANZAN CLAUDIU  PC DEVA

SECTIUNEA - PROGRAMARE

1. CLASELE 5-6
LOCUL I       STANCU MARA SORIN  PNC BUCURESTI
LOCUL II      BOSTAN RADU   PC BACAU
LOCUL II      TAUTU BOGDAN  PNC BUCURESTI
LOCUL III     STEFANESCU ANDREI  SC.59 BUCURESTI
MENTIUNE I    LUCA DANIEL   CC GIURGIU
MENTIUNE II   NICOLA LAURENTIU  PC CRAIOVA

2. CLASELE 7-8
LOCUL I       BERINDE RADU  PNC BUCURESTI
LOCUL II      COSTAN VICTOR  SC.59 BUCURESTI
LOCUL III     SABAU BOGDAN  CC AIUD
MENTIUNE I    MINCU ALEXANDRU  PC PLOIESTI
MENTIUNE II   PREOTEASA ALEXANDRU  PC CRAIOVA
MENTIUNE III  JULEAN SILVIU  PC ARAD

3. CLASELE 9-10
LOCUL I       PATRASCU MIHAI  PC CRAIOVA
LOCUL II      SABAU FLORIN  LIC.TEORETIC RESITA
LOCUL III     GHETU FLORIN  PC FOCSANI
MENTIUNE I    ADLER ANDREI  PNC BUCURESTI
MENTIUNE II   STAN BOGDAN   PC PLOIESTI
MENTIUNE III  DEAC ADRIAN   PC DEVA

4. CLASELE 11-12
LOCUL I       BATOG BOGDAN  PNC BUCURESTI
LOCUL II      DUMITRASCU IRINA  LIC.GR.MOISIL BUCURESTI
LOCUL III     STANCIU ADRIAN  PNC BUCURESTI
MENTIUNE I    ANDREI MARIUS  SC.59 BUCURESTI
MENTIUNE II   FANICIU LIVIU   LIC.INF.TIMISOARA
MENTIUNE III  MILOS CRISTIAN  CC LUGOJ
MENTIUNE III  BRATU BOGDAN  LIC.INF.TIMISOARA

